package mysort

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func partition(list Interface, l, r int) int {
	m := l - 1
	for j := l; j < r; j++ {
		if list.Less(j, r) {
			m++
			list.Swap(m, j)
		}
	}
	list.Swap(r, m+1)
	return m + 1
}

func qsort(list Interface, l int, r int) {
	if l >= r {
		return
	}
	m := partition(list, l, r)
	qsort(list, l, m-1)
	qsort(list, m+1, r)
}

func Qsort(list Interface) {
	qsort(list, 0, list.Len()-1)
}

func IsSorted(data Interface) bool {
	n := data.Len()
	for i := n - 1; i > 0; i-- {
		if data.Less(i, i-1) {
			return false
		}
	}
	return true
}

// func main() {
// 	var a IntSlice = []int{34, 345, 45, 435}
// 	Qsort(a)
// 	fmt.Println(a)
// }
